/* -*- Mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil; -*- */
/*
  RefObject (http://code.google.com/p/refobject/)
  Copyright (C) 2010-2011 MIURA Shirow (sharow)
*/

#include "RefListInternal.h"
#include "RefModuleInternal.h"


typedef struct {
    RefObject **mNodeArray;
    int mNodeArraySize;
    int mNumNode;
    RefObject *mRefAllocator;
} RefList;


static RefTypeObject *gListTypeObject = NULL;


RefTypeObject **
RefList_GetTypeObject(void)
{
    return &gListTypeObject;
}

int
RefList_IsValid(RefObject *aRefObject)
{
    return (RefObject_GetTypeObject(aRefObject) == &gListTypeObject);
}

static void
RefList_Destructor(RefObject *aRefObject)
{
    RefList *list;
    RefObject *refallocator;
    int i;
    list = RefObject_GetObject(aRefObject);
    refallocator = list->mRefAllocator;
    for (i = 0; i < list->mNumNode; i++) {
        RefObject_DecRef(list->mNodeArray[i]);
    }
    RefAllocator_Free(refallocator, list->mNodeArray);
    RefAllocator_Free(refallocator, aRefObject);
    RefObject_DecRef(refallocator);
}

static unsigned int
RefList_GetNextArraySize(unsigned int aPrevSize)
{
    if (aPrevSize == 0) {
        return 64U;
    } else if (aPrevSize < 1024) {
        return aPrevSize * 2;
    } else if (aPrevSize < (1024 * 1024)) {
        return (aPrevSize * 3) >> 1U;
    } else {
        /* very large array */
        return aPrevSize + 1024 * 16;
    }
}

static RefObject *
RefList_Create0(RefObject *aRefAllocator)
{
    RefObject *refobj;
    RefList *list;
    int array_size;
    array_size = RefList_GetNextArraySize(0);
    refobj = RefAllocator_Alloc(aRefAllocator, RefObject_SizeOf() + sizeof(*list));
    list = RefObject_Construct(refobj, &gListTypeObject, RefList_Destructor);
    list->mNodeArray = RefAllocator_Alloc(aRefAllocator, sizeof(*list->mNodeArray) * array_size);
    list->mNodeArraySize = array_size;
    list->mNumNode = 0;
    list->mRefAllocator = aRefAllocator;
    RefObject_IncRef(aRefAllocator);
    return refobj;
}

RefObject *
RefList_Create(void)
{
    return RefList_Create0(RefModule_GetSingletonAllocator());
}

RefObject *
RefList_CreateWithAllocator(RefObject *aRefAllocator)
{
    if (!RefAllocator_IsValid(aRefAllocator)) {
        return NULL;
    }
    return RefList_Create0(aRefAllocator);
}

static int
RefList_ResizeArray(RefList *aList, int aNewSize)
{
    RefObject **new_array;
    RefObject **old_array;
    int i;
    assert(aNewSize > aList->mNumNode);
    new_array = RefAllocator_Alloc(aList->mRefAllocator, sizeof(*new_array) * aNewSize);
    old_array = aList->mNodeArray;
    for (i = 0; i < aList->mNumNode; i++) {
        new_array[i] = old_array[i];
    }
    RefAllocator_Free(aList->mRefAllocator, aList->mNodeArray);
    aList->mNodeArray = new_array;
    aList->mNodeArraySize = aNewSize;
    return 0;
}

static int
RefList_ExtendArraySize(RefList *aList)
{
    return RefList_ResizeArray(aList, RefList_GetNextArraySize(aList->mNodeArraySize));
}

static int
RefList_ReductArraySize(RefList *aList)
{
    return RefList_ResizeArray(aList, aList->mNodeArraySize / 2);
}

int
RefList_Append(RefObject *aRefList, RefObject *aRefObject)
{
    RefList *list;
    int remain;
    list = RefObject_GetObject(aRefList);
    remain = list->mNodeArraySize - list->mNumNode;
    assert(remain >= 0);
    if (remain == 0) {
        if (RefList_ExtendArraySize(list)) {
            return 1;           /* allocation failed */
        }
        assert((list->mNodeArraySize - list->mNumNode) > 0);
    }
    list->mNodeArray[list->mNumNode] = aRefObject;
    list->mNumNode += 1;
    RefObject_IncRef(aRefObject);
    return 0;
}

int
RefList_Insert(RefObject *aRefList, int aIndex, RefObject *aRefObject)
{
    RefList *list;
    int i;
    list = RefObject_GetObject(aRefList);
    if (aIndex == list->mNumNode) {
        return RefList_Append(aRefList, aRefObject);
    }
    if (aIndex < 0 || aIndex > list->mNumNode) {
        return 1;
    }
    if ((list->mNodeArraySize - list->mNumNode) <= 0) {
        if (RefList_ExtendArraySize(list)) {
            return 1;           /* allocation failed */
        }
        assert((list->mNodeArraySize - list->mNumNode) > 0);
    }
    for (i = list->mNumNode; i >= aIndex; i--) {
        list->mNodeArray[i+1] = list->mNodeArray[i];
    }
    list->mNodeArray[aIndex] = aRefObject;
    list->mNumNode += 1;
    RefObject_IncRef(aRefObject);
    return 0;
}

RefObject *
RefList_TakeOutItem(RefObject *aRefList, int aIndex)
{
    RefList *list;
    RefObject *refobj;
    int i;
    list = RefObject_GetObject(aRefList);
    if (aIndex >= list->mNumNode) {
        return NULL;
    }
    refobj = list->mNodeArray[aIndex];
    for (i = aIndex; i < list->mNumNode; i++) {
        list->mNodeArray[i] = list->mNodeArray[i+1];
    }
    list->mNumNode -= 1;
    if ((list->mNodeArraySize - list->mNumNode) >= (list->mNumNode * 3)) {
        if (list->mNodeArraySize > 8) {
            RefList_ReductArraySize(list);
        }
    }
    return refobj;
}

int
RefList_DeleteItem(RefObject *aRefList, int aIndex)
{
    RefObject *refobj;
    refobj = RefList_TakeOutItem(aRefList, aIndex);
    if (refobj) {
        RefObject_DecRef(refobj);
        return 1;
    } else {
        return 0;
    }
}

RefObject *
RefList_GetItem(RefObject *aRefList, int aIndex)
{
    RefList *list;
    list = RefObject_GetObject(aRefList);
    if (aIndex < 0 || aIndex >= list->mNumNode) {
        return NULL;
    }
    return list->mNodeArray[aIndex];
}

int
RefList_GetSize(RefObject *aRefList)
{
    return ((RefList *)RefObject_GetObject(aRefList))->mNumNode;
}
